package visualizer.client.algorithms.sBst;

import visualizer.client.algorithms.AlgoResult;
import visualizer.client.bst.BNode;
import visualizer.client.bst.BinaryTree;

import java.util.List;

import static visualizer.client.utils.VisualizerUtils.DEFAULT_OUTER_COLOR;

/**
 * User: DDovzhenko
 * Date: 22.02.14
 * Time: 16:33
 */
public class SplayBSTUtils {
    private static List<AlgoResult> results;
    private static BinaryTree tree;

    public static void splay(BinaryTree tree, Integer key, List<AlgoResult> results) {
        SplayBSTUtils.results = results;
        SplayBSTUtils.tree = tree;
        tree.setRootNode(splay(tree.getRoot(), key));
    }

    private static BNode splay(BNode h, Integer key) {
        if (h == null) return null;

        int cmp1 = key.compareTo(h.getValue());

        if (cmp1 < 0) {
            if (h.getLeftBNode() == null) {
                return h;
            }
            int cmp2 = key.compareTo(h.getLeftBNode().getValue());
            if (cmp2 < 0) {
                h.getLeftBNode().setLeftBNode(splay(h.getLeftBNode().getLeftBNode(), key));
                h.setOuterColor("red");
                h.getLeftBNode().setOuterColor("red");
                results.add(new AlgoResult(tree.copyTree(true),
                        "Выполняем двойную ротацию вправо-вправо: первая ротация вправо для узла с ключом " + h.getValue()
                                + ", вторая ротация вправо для узла с ключом " + h.getLeftBNode().getValue()));
                h.setOuterColor(DEFAULT_OUTER_COLOR);
                h.getLeftBNode().setOuterColor(DEFAULT_OUTER_COLOR);
                h = rotateRight(h);
            } else if (cmp2 > 0) {
                h.getLeftBNode().setRightBNode(splay(h.getLeftBNode().getRightBNode(), key));
                if (h.getLeftBNode().getRightBNode() != null) {
                    h.setOuterColor("red");
                    h.getLeftBNode().setOuterColor("red");
                    results.add(new AlgoResult(tree.copyTree(true),
                            "Выполняем двойную ротацию влево-вправо: ротация влево для узла с ключом " + h.getLeftBNode().getValue()
                                    + ", ротация вправо для узла с ключом " + h.getValue()));
                    h.setOuterColor(DEFAULT_OUTER_COLOR);
                    h.getLeftBNode().setOuterColor(DEFAULT_OUTER_COLOR);
                    h.setLeftBNode(rotateLeft(h.getLeftBNode()));
                } else {
                    h.setOuterColor("red");
                    results.add(new AlgoResult(tree.copyTree(true), "Выполняем одиночную ротацию вправо для узла с ключом " + h.getValue()));
                    h.setOuterColor(DEFAULT_OUTER_COLOR);
                }
            } else {
                h.setOuterColor("red");
                results.add(new AlgoResult(tree.copyTree(true), "Выполняем одиночную ротацию вправо для узла с ключом " + h.getValue()));
                h.setOuterColor(DEFAULT_OUTER_COLOR);
            }

            return h.getLeftBNode() == null ? h : rotateRight(h);
        } else if (cmp1 > 0) {
            if (h.getRightBNode() == null) {
                return h;
            }

            int cmp2 = key.compareTo(h.getRightBNode().getValue());
            if (cmp2 < 0) {
                h.getRightBNode().setLeftBNode(splay(h.getRightBNode().getLeftBNode(), key));
                if (h.getRightBNode().getLeftBNode() != null) {
                    h.setOuterColor("red");
                    h.getRightBNode().setOuterColor("red");
                    results.add(new AlgoResult(tree.copyTree(true),
                            "Выполняем двойную ротацию вправо-влево: ротация вправо для узла с ключом " + h.getRightBNode().getValue()
                                    + ", ротация влево для узла с ключом " + h.getValue()));
                    h.setOuterColor(DEFAULT_OUTER_COLOR);
                    h.getRightBNode().setOuterColor(DEFAULT_OUTER_COLOR);
                    h.setRightBNode(rotateRight(h.getRightBNode()));
                } else {
                    h.setOuterColor("red");
                    results.add(new AlgoResult(tree.copyTree(true), "Выполняем одиночную ротацию влево для узла с ключом " + h.getValue()));
                    h.setOuterColor(DEFAULT_OUTER_COLOR);
                }
            } else if (cmp2 > 0) {
                h.getRightBNode().setRightBNode(splay(h.getRightBNode().getRightBNode(), key));
                h.setOuterColor("red");
                h.getRightBNode().setOuterColor("red");
                results.add(new AlgoResult(tree.copyTree(true),
                        "Выполняем двойную ротацию влево-влево: первая ротация влево для узла с ключом " + h.getValue()
                                + ", вторая ротация влево для узла с ключом " + h.getRightBNode().getValue()));
                h.setOuterColor(DEFAULT_OUTER_COLOR);
                h.getRightBNode().setOuterColor(DEFAULT_OUTER_COLOR);
                h = rotateLeft(h);
            } else {
                h.setOuterColor("red");
                results.add(new AlgoResult(tree.copyTree(true), "Выполняем одиночную ротацию влево для узла с ключом " + h.getValue()));
                h.setOuterColor(DEFAULT_OUTER_COLOR);
            }

            return h.getRightBNode() == null ? h : rotateLeft(h);
        } else {
            return h;
        }
    }

    private static BNode rotateRight(BNode h) {
        BNode x = h.getLeftBNode();
        h.setLeftBNode(x.getRightBNode());
        x.setRightBNode(h);
        return x;
    }

    private static BNode rotateLeft(BNode h) {
        BNode x = h.getRightBNode();
        h.setRightBNode(x.getLeftBNode());
        x.setLeftBNode(h);
        return x;
    }

    public static boolean search(BinaryTree tree, int key, List<AlgoResult> results) {
        SplayBSTUtils.results = results;
        SplayBSTUtils.tree = tree;
        return search(tree.getRoot(), key);
    }

    private static boolean search(BNode node, int key) {
        node.setOuterColor("red");
        if (key < node.getValue()) {
            results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: " + key + " < " + node.getValue() + ", обрабатываем левое поддерево"));
            if (node.getLeftBNode() != null) {
                node.setOuterColor(DEFAULT_OUTER_COLOR);
                return search(node.getLeftBNode(), key);
            } else {
                node.setInnerColor("lightgreen");
                node.setOuterColor("green");
                return false;
            }
        } else if (key > node.getValue()) {
            results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: " + key + " > " + node.getValue() + ", обрабатываем правое поддерево"));
            if (node.getRightBNode() != null) {
                node.setOuterColor(DEFAULT_OUTER_COLOR);
                return search(node.getRightBNode(), key);
            } else {
                node.setInnerColor("lightgreen");
                node.setOuterColor("green");
                return false;
            }
        } else {
            node.setInnerColor("lightgreen");
            node.setOuterColor("green");
            return true;
        }
    }
}
